package LimitedTimeGame.Day_0205;

/**
 * @author zxc
 * @date 2023/02/05 09:05
 **/

/**
 * 题目 ：穿过迷宫的最少移动次数
 * 题目详述 ：
 * 在一个n*n的网格上构建了新的迷宫地图，蛇的长度为 2，也就是说它会占去两个单元格。
 * 蛇会从左上角（(0, 0)和(0, 1)）开始移动。
 * 我们用 0 表示空单元格，用 1 表示障碍物。蛇需要移动到迷宫的右下角（(n-1, n-2)和(n-1, n-1)）。
 * 每次移动，蛇可以这样走：
 * 如果没有障碍，则向右移动一个单元格。并仍然保持身体的水平／竖直状态。
 * 如果没有障碍，则向下移动一个单元格。并仍然保持身体的水平／竖直状态。
 * 如果它处于水平状态并且其下面的两个单元都是空的，就顺时针旋转 90 度。蛇从（(r, c)、(r, c+1)）移动到 （(r, c)、(r+1, c)）。
 * 如果它处于竖直状态并且其右面的两个单元都是空的，就逆时针旋转 90 度。蛇从（(r, c)、(r+1, c)）移动到（(r, c)、(r, c+1)）。
 * 返回蛇抵达目的地所需的最少移动次数。
 * 如果无法到达目的地，请返回-1。
 *
 * 提示：
 * 2 <= n <= 100
 * 0 <= grid[i][j] <= 1
 * 蛇保证从空单元格开始出发。
 *
 */
public class MinimumMoves {
    /**
     * 思路 ：
     * 动态规划，来解决此贪吃蛇问题;
     *
     * 假设f(x,y,status)为状态为status(0,表示水平状态;1，表示垂直状态) && 贪吃蛇尾部节点为(x,y)，所抵达目的地所需要的最少移动次数;
     * 注意 ：此处的(x,y)为贪吃蛇尾部节点坐标;同时，status代表了贪吃蛇当前状态（处于水平/垂直状态;）
     * ===>  贪吃蛇尾节点(x,y) + 贪吃蛇所处状态（水平/垂直状态）,即能够唯一确定贪吃蛇所在位置（即，唯一确定其所占据的两个格子;）
     *
     * 状态转移方程 ：
     * （1）当status == 0时，（即，贪吃蛇处于水平状态下）
     *  a.坐标(x，y) && 坐标(x,y+1)都是可达到的情况下，即 f(x,y,0) = f(x,y+1,0) + 1;
     *  b.坐标(x,y) && 坐标(x+1,y)都是可到达的情况下，即f(x,y,0) = f(x+1,y,0) + 1;
     * （2）当status == 1时，（即，贪吃蛇处于垂直状态下）
     *  a.坐标(x，y) && 坐标(x,y+1)都是可达到的情况下，即 f(x,y,1) = f(x,y+1,1) + 1;
     *  b.坐标(x,y) && 坐标(x+1,y)都是可到达的情况下，即f(x,y,1) = f(x+1,y,1) + 1;
     * （3）当坐标(x,y) && 坐标(x+1,y+1) && (坐标(x+1,y) || 坐标(x,y+1))是可到达的情况下，
     *  ===》 f(x,y,0) = f(x,y,1) + 1;  ||  f(x,y,1) = f(x,y,0) + 1;
     *
     * （4）注意的是，由于所要求解的是到达当前位置所需要的最少移动次数;
     * （即，若是某个位置到达不了的话，则将其到达该位置所需要的最少移动次数 设置为Integer.MAX_VALUE）
     * @param grid
     * @return
     */
    public int minimumMoves(int[][] grid) {
        final int MAX_VALUE = Integer.MAX_VALUE / 2;
        int len = grid.length;
        int[][][] dp = new int[len][len][2];
        for(int i = 0 ; i < len ;i++){
            for(int j = 0; j < len ;j++){
                dp[i][j][0] = MAX_VALUE;
                dp[i][j][1] = MAX_VALUE;
            }
        }
        // 初始化状态 ：尾节点坐标为(0,0) && 其处于水平状态;
        dp[0][0][0] = 0;

        // 遍历grid数组中的所有节点
        for(int i = 0 ; i < len ; i++){
            for(int j = 0 ; j < len ; j++){
                // 判断该位置是否为合法位置;
                // 水平情况 ：
                boolean isHorizontal = j + 1 < len && grid[i][j] == 0 && grid[i][j + 1] == 0;
                // 垂直情况 ：
                boolean isVertical = i + 1 < len && grid[i][j] == 0 && grid[i + 1][j] == 0;

                // （1）贪吃蛇处于水平状态 && 贪吃蛇通过向右移动到达当前状态;
                if(j > 0 && isHorizontal){
                   dp[i][j][0] = Math.min(dp[i][j][0] , dp[i][j - 1][0] + 1);
                }
                // （2）贪吃蛇处于水平状态 && 贪吃蛇通过向下移动到达当前状态;
                if(i > 0 && isHorizontal){
                    dp[i][j][0] = Math.min(dp[i][j][0] , dp[i - 1][j][0] + 1);
                }
                // （3）贪吃蛇处于垂直状态 && 贪吃蛇通过向右移动到达当前状态;
                if(j > 0 && isVertical){
                    dp[i][j][1] = Math.min(dp[i][j][1] , dp[i][j - 1][1] + 1);
                }
                // （4）贪吃蛇处于垂直状态 && 贪吃蛇通过向下移动到达当前状态;
                if(i > 0 && isVertical){
                    dp[i][j][1] = Math.min(dp[i][j][1] , dp[i - 1][j][1] + 1);
                }
                // （5）贪吃蛇处于水平/垂直状态，贪吃蛇通过顺时针/逆时针选择到达当前状态;
                if(isHorizontal && isVertical && grid[i + 1][j + 1] == 0){
                    int temp = dp[i][j][0];
                    dp[i][j][0] = Math.min(dp[i][j][0] , dp[i][j][1] + 1);
                    dp[i][j][1] = Math.min(dp[i][j][1] , temp + 1);
                }
            }
        }
        return dp[len - 1][len - 2][0] == MAX_VALUE ? -1 : dp[len - 1][len - 2][0];
    }
    /**
     * 分析 ：
     * 1.贪吃蛇当前位置 ：(x,y,status)
     *  ===> (x,y)，为贪吃蛇尾部节点位置;status，为贪吃蛇当前状态（水平/垂直状态）;
     * 2.要到达当前贪吃蛇位置，有三种可能性：
     * （1）(x,y-1,status)向右移动到达(x,y,status);
     * （2）(x-1,y,status)向下移动到达(x,y,status);
     * （3）(x,y,1-status)逆时针/顺时针进行旋转到达(x,y,status);
     *  ===> 即，第三种情况就是 贪吃蛇尾节点是相同的 && （水平状态 -> 垂直状态 || 垂直状态 -> 水平状态）;
     *
     */
}
